ATM (asynchronous transfer mode) is a communication system for sending or receiving at a high speed all data, to be transmitted, which have been divided into units called “cells” of 53 octets (one octet=8 bits). ATM is suitable for the transfer of large-capacity data, such as multimedia data, and constitutes a basic technique of broadband ISDN.
In ATM, multiplex communication is carried out, and, in addition, the transmission rate can be regulated at a desired value by setting the number of cells sent per given time (cell rate) to a desired value. By virtue of this, even when voices (audio), static images, moving images and the like are present together in an object to be sent, the object can be properly transmitted.
An ATM switch performs large-capacity, high-speed digital switching and mediates communication between terminals. An example of switching conducted by the ATM switch is to cell multiplex a plurality of ATM lines into a single physical transmission path followed by send of the multiplexed cells.
In this case, regarding the sequence of read of data in each ATM line (i.e., the sequence of send of cell in each line), also from the viewpoint of sending data at a proper speed, in sending cells, the individual cells should be dispersed, if possible, at equal spacings, so as to avoid the send of cells in the concentrated state at a time in the same line according to the rate of each line.
For example, in the control of send of cells using a time slot for designating the sequence of send of the individual cells, for example, in order to reduce a burst property at an output port in each ATM line, scheduling should be carried out to properly allocate the individual cells in the same line to respective positions dispersed within the time slot.
For each line. PCR (peak cell rate) is used as a value for designating the maximum speed for sending the cells in the line. PCR indicates the maximum speed at which cells can be transferred in ATM. Further, the minimum spacing for transferring the cells in the same line is determined by the PCR value. Hereinafter, the term “PCR value” in the present specification is used for indicating the number of cells which can be transferred within one time slot in each line. That is, for example, in a line such that the PCR value is “4,” four cells can be sent per turn of the time slot.
An example of a conventional technique for allocating cells in each line respectively to positions dispersed within the time slot will be explained. FIG. 4 is a diagram illustrating an example of a conventional scheduling technique for allocating individual cells respectively to positions dispersed within a time slot, wherein the length of the time slot is 16.
At the outset, a cell read sequence management table is provided which is a table having a length corresponding to the maximum number of cells allocable to the time slot (hereinafter, this number of cells is referred to as STENO).
Elements, the number of which is equal to the number of cells transferred within one time slot in each data to be transferred (that is, corresponding to the PCR value of each data), are ensured together within the cell read sequence management table. In the example shown in FIG. 4, the PCR value of ATM lines (or data to be transferred) indicated by “A” and “B” is “2,” the PCR value of “C” is “1,” and the elements are successively ensured from the head element within the cell read sequence management table.
In the time slot, slots respectively to which the cells are allocated are designated corresponding to the sequence of individual elements in the cell read sequence management table, and the cells in each line to be sent are allocated respective to the designated positions. In the example shown in FIG. 4, the cells of “A” are allocated to slots corresponding to numbers 1 and 2, and the cells of “B” are allocated to slots corresponding to numbers 3 and 4.
In the time slot, the cells allocated to the respective slots are successively sent clockwise. That is, in the sequence in the cell read sequence management table, 1, 9, 5, 13, . . . are sent in that order. Thus, the cells in the same line are sent in the dispersed state. For example, in FIG. 4, the two cells in “A” or “B” are allocated to positions which face each other within the time slot. Therefore, at a rate for sending the two cells in one turn, the cells are successively sent at equal spacing.
Thus, scheduling of the cell read sequence management table based on the PCR value in each ATM line in a service object followed by the control of read according to the scheduled cell read sequence management table can ensure the transfer rate in the transfer of each cell in each ATM line of the service object.
Successive positions in the sequence within the cell read sequence management table can be converted to respective positions dispersed within the time slot, for example, by the following method.
FIG. 2 shows an example of calculation in a method for converting the positions of the cell read sequence management table to respective positions within the time slot, and FIG. 3 shows a list of the results of the conversion.
In this example, a time slot length of 16 is taken as an example. The same is true of other cases where the length is a value obtained by raising 2 to the nth power wherein n is an integer (for example, 32, 64, . . . etc.). Here the length of the cell read sequence management table is equal to the length of the time slot, and thus can be expressed in terms of binary number of which the number of digits is calculated by equation log 2 L wherein L is the length of the table. In this example, log 2 (16)=4 (digits).
As shown in FIG. 2, “1” is first subtracted from each value in the sequence, and the value thus obtained is expressed in terms of binary number of four digits. The numerical values (“0” or “1”) of the individual digits expressed in terms of binary number are converted so as to be reversed in sequence. That is, MOB (most significant bit) side and LSB (least significant bit) side in the value expressed in terms of binary number of four digits are reversed in sequence to obtain a new binary number. “1” is added to the binary number thus obtained to determine a value which is regarded us the corresponding time slot position.
For example, in the “8th” within the cell read sequence management table, the subtraction of “1” from this value followed by the expression of the obtained value in terms of a four-digit binary number gives “0111” (=7). These individual digits are rearranged so as to be reversed in sequence to give a value of “1110” (=14). Finally, “1” is added to thin value to obtain the corresponding time slot position “15” as the conversion result.
Here values obtained by raising 2 to the nth power, wherein n is an integer, are used as the maximum rate (PCR value) of the band in each service ATM line, and the cell read sequence management table is scheduled based on the PCR values. The use of values obtained by raising 2 to the nth power, wherein n is an integer, (i.e., 1, 2, 4, 8, . . . etc.) as the PCR value is common in the art. In this method, the properties of the binary number can be utilized, and the processing can be simplified.
In particular, this conversion method is suitable in the case where, in the cell read sequence management table, elements corresponding to the PCR value (value obtained by raising 2 to the nth power wherein n is an integer) are continuously ensured from a position which is one ahead of the position corresponding to a value obtained by multiplying the PCR value by an integer, that is, a position which is next to the position corresponding to a value obtained by multiplying the PCR value by an integer. The elements, which have been ensured here, are dispersed at equal spacings in the time slot. Further, ensuring the elements corresponding to the PCR value (value obtained by raising 2 to the nth power wherein n is an integer) from one ahead of the position corresponding to a value obtained by multiplying the PCR value by an integer can be simply achieved by arranging the elements corresponding to the PCR value in each line in the descending order of the PCR values from the head.
For example, in the example shown in FIG. 4, the three lines “A,” “B,” and “C” having respective PER values of “2,” “2,” and “1” are successively arranged in the descending order of the PCR values to ensure the elements corresponding to the PCR values in the cell read sequence management table. This permits the elements to be allocated at equal spacings to the time slot, whereby cells in each line are sent at equal intervals.
Further, to the contrary, in the prior art, in order to transfer cells sent from each line at an even rate, in the cell read sequence management table, the elements for each line are successively arranged so that the PCR values are in descending order by the above method.
In the ATM switch which transfers cells in each of the ATM lines, however, data is not always sent at a stationary data transfer rate. That is, in some cases, the transfer of data is ended halfway in each line, or, on the contrary, in some cases, in each line, new data transfer is started.
For this reason, in the conventional ATM switch, as described above, the individual lines are scheduled from the head of the cell read sequence management table in the descending order of PCR values and, at the same time, so as to avoid the occurrence of an unused idle area between lines, and the positions of each line within the cell read sequence management table are properly updated.
Next, a conventional scheduling system will be explained wherein a cell read sequence management table is scheduled by the above method.
FIG. 6 is a block diagram showing the construction of a scheduling system 10a for controlling the read of cells in a conventional ATM line.
Referring now to FIG. 6, in a conventional scheduling system 100a, data received in a line setting interface 10 is first supplied to a schedule computation section 20a, and calculation for scheduling of the cell read management table is executed.
An allocation processor 30 sets, in a time slot 40, the result of scheduling calculated by the schedule computation section 20a. In other words, the allocation processor 30 converts the individual elements in the cell read management table to respective positions in the time slot 40 by the conversion method shown in FIGS. 2 and 3.
Shaping service, which has assured the rate of each ATM line, can be carried out by reading an ATM line, input into the device, from a connection input queue 50 to a shaping service output queue 60 according to the time slot setting.
The construction and operation of the conventional schedule computation section 20a shown in FIG. 6 are as follows.
Specifically, data sent from the line setting interface 10 is processed in a parameter processor, and is output to a schedule object computation section. Upon new receive of line or delete of line, the schedule object computation section computes a line, in the cell read sequence management table, of which the position is to be changed. In the conventional schedule computation section 20, ATM lines as the schedule change object are a part of lines having the same PCR value as PCR values of lines, of which a line is to be newly received or deleted, and all of lines having a smaller PCR value.
A schedule clear section clears the cell read sequence management table of which the schedule is to be changed. The schedule computation section performs scheduling in the descending order of PCR values of lines (i.e., a line having a larger PCR value among the lines as the computed schedule change object is scheduled in an earlier stage) in a successive manner from the head of idle areas in the cell read sequence 125 management table. The reason for this is that scheduling in the descending order of PCR values of lines can provide better receive efficiency of the cell read sequence management table from the viewpoint of assuring the rate of ATM lines to be shaped.
Further, as described above, when PCR values are values obtained by raising 2 to the nth power, wherein n is an integer, scheduling in the descending order of PCR values of lines (i.e., a line having a larger PCR value is scheduled in an earlier stage) from the head of idle areas in the cell read sequence management table can ensure positions assuring the rate in the cell read management table.
Here when lines have not been aligned, that is, when the individual lines have been successively scheduled from the head in idle areas of the cell read sequence management table without alignment, however, the arrangement of lines in the descending order is broken and, consequently, there is a fear of the assurance of line rate being lost.
FIG. 5 is a diagram illustrating the read of cells in the case where the arrangement of lines in descending order in a cell read sequence management table has been broken. In FIG. 5, three lines shown in FIG. 4 are arranged in the order of “C,” “A,” and “B,” that is, in the order of PCR values “1,” “2,” and “2.” Unlike the example of FIG. 4 in which cells have been sent at equal intervals, in the lines “A” and “B,” cells are sent at uneven intervals which do not satisfy a send interval requirement indicated by the PCR value.
Therefore, in the prior art, when a schedule is newly received or changed, as described above, the individual lines as the processing object should be aligned.
As described above, in the conventional scheduling system, every time when a change has occurred in a line to be cataloged in the cell read sequence management table, troublesome processing should be carried out such that all the cataloged lines are aligned in the descending order of PCR values and rearranged from the head.
An example of a conventional measure devised to deal with this problem is as follows. In order that, among lines cataloged in the cell read sequence management table, lines having a larger PCR value than the PCR value of the line, in which the change has occurred, do not undergo a change in the position within the cell read sequence management table upon the rescheduling, the object of the position conversion processing is limited only to a part of lines having the same PCR value as the PCR value of the line, in which the change has occurred, and all the lines having smaller PCR values than the line, in which the change has occurred, followed by computation of rescheduling. Even when the object of the rescheduling is limited to a narrower range in this way, however, there remains the necessity of executing troublesome processing such that, every time when a change, such as new addition of a line, has occurred, the lines are aligned and rearranged.